package acwing._1_1AlgorithmBasic._5DynamicProgramming;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @Project : AlgorithmLearning
 * @Package : ACWing._1_1AlgorithmBasic._5DynamicProgramming
 * @File : Q0899.java
 * @Author : WangRuoyu
 * @Date 2023/11/25 16:13
 */

public class Q0899 {
    private static boolean check(String a, String b, int k) {
        int[][] f = new int[a.length() + 1][b.length() + 1];
        for (int i = 0; i <= a.length(); i++) f[i][0] = i;
        for (int i = 0; i <= b.length(); i++) f[0][i] = i;

        for (int i = 1; i <= a.length(); i++) {
            for (int j = 1; j <= b.length(); j++) {
                f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + 1;
                if (a.charAt(i - 1) == b.charAt(j - 1)) f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
                else f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + 1);
            }
        }

        return f[a.length()][b.length()] <= k;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int m = Integer.parseInt(line[0]);
        int n = Integer.parseInt(line[1]);

        String[] strs = new String[m];

        for (int i = 0; i < m; i++) {
            strs[i] = br.readLine().split(" ")[0];
        }
        for (int i = 0; i < n; i++) {
            line = br.readLine().split(" ");
            String s = line[0];
            int k = Integer.parseInt(line[1]);
            int res = 0;
            for (int j = 0; j < m; j++) {
                if (check(strs[j], s, k)) res++;
            }
            System.out.println(res);
        }
    }
}